//
// Created by lights on 2024/7/1.
//

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

#define V 6 // 节点数量

// 找到距离集合S最近的节点
int minDistance(vector<int>& dist, vector<bool>& sptSet) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}

// 打印从源节点到所有其他节点的最短距离
void printSolution(vector<int>& dist) {
    cout << "Vertex \t Distance from Source\n";
    for (int i = 0; i < V; i++) {
        cout << i << " \t\t" << dist[i] << endl;
    }
}

// 打印每一步的过程
void printStep(vector<int>& dist, vector<bool>& sptSet) {
    cout << "Vertex \t Distance \t Shortest Path Tree Set\n";
    for (int i = 0; i < V; i++) {
        cout << i << " \t" << dist[i] << " \t\t" << sptSet[i] << endl;
    }
    cout << "--------------------------------\n";
}

// Dijkstra算法
void dijkstra(vector<vector<int>>& graph, int src) {
    vector<int> dist(V, INT_MAX); // 源节点到其他节点的最短距离
    vector<bool> sptSet(V, false); // 是否包含在最短路径树集合中

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }

        // 打印每一步的过程
        printStep(dist, sptSet);
    }

    // 打印最终结果
    printSolution(dist);
}

int main() {
    vector<vector<int>> graph = {
            {0, 60, 110, 0, 13},
            {0, 0, 20, 60, 2},
            {0, 0, 0, 4, 0},
            {7, 0, 6, 0, 0},
            {0, 3, 9, 2, 0}
    };

    dijkstra(graph, 0);

    return 0;
}